勒让德筛法

在数学上，勒让德筛法（Legendre sieve）是现代筛法中最简单的，其以阿德里安-马里·勒让德为名。这筛法是埃拉托斯特尼筛法的概念的推广，用以找出一个给定的集合中质数数量的上下界。由于这筛法是埃拉托斯特尼概念的简单推广之故，因此有时又称作勒让德—埃拉托斯特尼筛法（Legendre–Eratosthenes sieve）。^[1]

勒让德等式[编辑]

勒让德筛法的中心概念可以下列等式表示，有时这等式又称作勒让德等式（Legendre identity）：

S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,

在其中， $A$ 是一个整数集、 $P$ 是不同质数的乘积， $\mu$ 是默比乌斯函数；而 $A_{d}$ 是 $A$ 中可被 $d$ 除尽的元素的集合，是 $A$ 的子集；而 $S(A,P)$ 的定义如次：

S(A,P)=|\{n:n\in A,\gcd(n,P)=1\}|

换句话说， $S(A,P)$ 指的是 $A$ 中与 $P$ 互质的元素的个数。

当注意的是，在多数情况中， $A$ 是所有小于特定实数 $X$ 的整数的集合， $P$ 是所有小于等于特定整数 $z$ 的质数的乘积，且 $z<X$ ，因此勒让德等式可以下式表示（其中 $\lfloor X\rfloor$ 是下取整函数）：

{\begin{aligned}S(A,P)={}&\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\[6pt]={}&\lfloor X\rfloor -\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor \\[4pt]&{}-\sum _{p_{1}<p_{2}<p_{3}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots +\mu (P)\left\lfloor {\frac {X}{P}}\right\rfloor \end{aligned}}

至此勒让德等式衍生自埃拉托斯特尼筛法变得明朗：上式中的第一项表示所有小于 $X$ 的整数，第二项则去掉其中至少是一个质数倍数的数，第三项则将其中至少是两个质数倍数的数给补回（会有第三项是因为第二项会把两个质数倍数的数给错误地删去两次之故），但因为这样又多补回一次至少是三个质数倍数的数，因此第三项中又要将之删去，其余以此类退，直到所有质数的 $2^{\pi (z)}$ 个组合全部都考虑过为止。（ $\pi (z)$ 指的是小于 $z$ 的质数的数量）。